package com.example.question.bt.backtrack2;

public class Code04_79 {
    public static void main(String[] args) {
        // [["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
        //"ABCESEEEFS"
        char[][] board = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'E', 'S'}, {'A', 'D', 'E', 'E'}};
//        char[][] board = new char[][]{{'a'}};
        Code04_79 code = new Code04_79();
        System.out.println("code.exist(board, \"ABCESEEEFS\") = " + code.exist(board, "ABCESEEEFS"));
    }

    public boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (chars[0] == board[i][j]) {
                    int count = exist(board, new boolean[board.length][board[0].length], i, j, chars, 0);
                    if (count > 0) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    // 找到一个节点之后  往上下左右四个方向  分别遍历
    private Integer exist(char[][] board, boolean[][] visited, Integer row, Integer col, char[] word, Integer index) {
        if (index == word.length) {
            return 1;
        }
        if (row >= board.length || col >= board[0].length || row < 0 || col < 0) {
            return 0;
        }
        if (!visited[row][col] && board[row][col] == word[index]) {
            visited[row][col] = true;
            int ret3 = exist(board, visited, row, col + 1, word, index + 1);
            int ret4 = exist(board, visited, row, col - 1, word, index + 1);
            int ret1 = exist(board, visited, row + 1, col, word, index + 1);
            int ret2 = exist(board, visited, row - 1, col, word, index + 1);
            // 回溯的时候清场一下
            visited[row][col] = false;
            return ret1 + ret2 + ret3 + ret4;
        }
        return 0;
    }
}
